


public class Test {

    public MySingleList.ListNode getIntersectionNode(MySingleList.ListNode headA, MySingleList.ListNode headB) {
        MySingleList.ListNode pl = headA;
        MySingleList.ListNode ps = headB;
        int lenA = 0;
        int lenB = 0;
        //1. 遍历两个链表计算长度
        while (pl != null) {
            lenA++;
            pl = pl.next;
        }

        while (ps != null) {
            lenB++;
            ps = ps.next;
        }
        // 走到这里，如果没有进入下面if语句
        // pl和ps此时都为null,需要重新修正指向
        pl = headA;
        ps = headB;
        int len = lenA - lenB;
        if (len < 0) {
            //修正一下 pl和ps的指向
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        //代码执行到这里，len一定是正数
        //pl一定指向最长的链表，ps一定指向最短的链表

        //2. 让最长链表先走差值步
        while (len > 0) {
            pl = pl.next;
            len--;
        }

        //3. 同时开始一步一步走 4. 相遇就是相遇点
        //包含pl和ps都为null的情况
        while (pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }

        //没有相交的情况
        if (pl == null) {
            return null;
        }
        return pl;
        //return pl;//包含了没有相交的情况。
    }


    public MySingleList.ListNode getIntersectionNode2(MySingleList.ListNode headA, MySingleList.ListNode headB) {


        MySingleList.ListNode curA = headA;
        MySingleList.ListNode curB = headB;
        //1. 分别求链表长度
        int len1 = 0;
        int len2 = 0;
        while (curA != null) {
            len1++;
            curA = curA.next;
        }
        while (curB != null) {
            len2++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        //2. 最长的走差值步
        if (len1 > len2) {
            for (int i = 0; i < len1 - len2; i++) {
                curA = curA.next;
            }
        } else {
            for (int i = 0; i < len2 - len1; i++) {
                curB = curB.next;
            }
        }

        //3. 同时走//4. 相遇的就是相遇点
        while (curA != curB) {
            curA = curA.next;
            curB = curB.next;
        }
        return curA;
    }


    //将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
    public static MySingleList.ListNode mergeTwoLists(MySingleList.ListNode head1, MySingleList.ListNode head2) {

        //虚拟节点，起标识作用
        MySingleList.ListNode newH = new MySingleList.ListNode(-1);
        MySingleList.ListNode tmpH = newH;
        while (head1 != null && head2 != null) {
            if (head1.val < head2.val) {
                tmpH.next = head1;
                head1 = head1.next;
            } else {
                tmpH.next = head2;
                head2 = head2.next;
            }
            tmpH = tmpH.next;
        }

        //上面代码走完head1、head2可能还有剩余节点需要拼接
        if (head1 != null) {
            tmpH.next = head1;
        }
        if (head2 != null) {
            tmpH.next = head2;
        }
        return newH.next;
    }


    public static void main5(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addLast(8);
        mySingleList.addLast(12);
        mySingleList.addLast(23);
        mySingleList.addLast(12);
        mySingleList.addLast(8);
    }


    public static void main3(String[] args) {
        MySingleList mySingleList1 = new MySingleList();
        mySingleList1.addLast(8);
        mySingleList1.addLast(12);
        mySingleList1.addLast(23);
        mySingleList1.addLast(45);
        mySingleList1.addLast(90);

        mySingleList1.display();

        MySingleList mySingleList2 = new MySingleList();
        mySingleList2.addLast(5);
        mySingleList2.addLast(11);
        mySingleList2.addLast(22);
        mySingleList2.addLast(25);
        mySingleList2.display();
        System.out.println("===========================");

        MySingleList.ListNode head = mergeTwoLists(mySingleList1.head, mySingleList2.head);

        mySingleList1.display(head);
    }


    public static void main2(String[] args) {
        MySingleList mySingleList = new MySingleList();
        mySingleList.addLast(13);
        mySingleList.addLast(11);
        mySingleList.addLast(23);
        mySingleList.addLast(12);
        mySingleList.addLast(34);
        //mySingleList.removeAllKey(34);
        mySingleList.display();
        //MySingleList.ListNode ret = mySingleList.reverseList(mySingleList.head);
        //mySingleList.display(ret);

        MySingleList.ListNode listNode2 = mySingleList.middleNode(mySingleList.head);
        System.out.println(listNode2.val);
    }


    public static void main1(String[] args) {
        MySingleList mySingleList = new MySingleList();
        //mySingleList.createLink();
        //mySingleList.display();
        /*mySingleList.addFirst(12);
        mySingleList.addFirst(23);
        mySingleList.addFirst(90);
        mySingleList.addFirst(34);*/
        mySingleList.addLast(12);
        mySingleList.addLast(45);
        mySingleList.addLast(23);
        mySingleList.addLast(90);

        mySingleList.display();
        System.out.println(mySingleList.contains(90));

        System.out.println(mySingleList.size());

        mySingleList.addIndex(1, 666);
        mySingleList.display();

        mySingleList.remove(6);
        mySingleList.display();

        mySingleList.clear();
        mySingleList.display();

    }
}
